package medium.array;

/**
 * <a href="https://leetcode-cn.com/problems/search-a-2d-matrix">74. 搜索二维矩阵</a>
 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 *   每行中的整数从左到右按升序排列。
 *   每行的第一个整数大于前一行的最后一个整数。
 * 示例 1：
 *   输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
 *   输出：true
 * 示例 2：
 *   输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
 *   输出：false
 * 提示：
 *   m == matrix.length
 *   n == matrix[i].length
 *   1 <= m, n <= 100
 *   -104 <= matrix[i][j], target <= 104
 * @author 刘学松
 * @date 2021-03-30 18:45
 */
public class 搜索二维矩阵 {
    public static void main(String[] args) {
        int[][] matrix = {{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
        int target = 3;
        System.out.println(searchMatrix(matrix, target));
    }

    public static boolean searchMatrix(int[][] matrix, int target) {
        int height = matrix.length;
        int width = matrix[0].length;
        int i = 0;
        int j = width-1;
        while (i < height && j>=0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] < target) {
                i++;
            } else {
                j--;
            }
        }
        return false;
    }
}
